﻿package tools;
import java.util.Arrays;

public class SortDemo {
	public static void main(String[] args) {
		int[] int_array_a = { 4, 6, 7, 8, 10, 1, 3, 2, -1 };
		SortDemo ms = new SortDemo();
		ms.choice(int_array_a);
		ms.charu(int_array_a);
		ms.maopao(int_array_a);
		ms.reverse(int_array_a);
	}

	/**
	 * 冒泡排序——交换排序的一种 方法：相邻两元素进行比较，如有需要则进行交换， 每完成一次循环就将最大元素排在最后（如从小到大排序），
	 * 下一次循环是将其他的数进行类似操作。
	 */
	private void maopao(int[] a) {
		int len = a.length;
		for (int i = len - 1; i > 0; i--) {
			for (int j = 0; j < i; j++) {
				if (a[j] > a[j + 1]) {
					swap(a, j, j + 1);
				}
			}
		}
		print_array(a);
	}

	/**
	 * 直接选择排序法——选择排序的一种 方法：每一趟从待排序的数据元素中选出最小（或最大）的一个元素,
	 * 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
	 */
	private void choice(int[] a) {
		int len = a.length;
		for (int i = 0; i < len; i++) {
			for (int j = i + 1; j < len; j++) {
				if (a[i] > a[j]) {
					swap(a, i, j);
				}
			}
		}
		print_array(a);
	}

	/**
	 * 插入排序 方法：将一个记录插入到已排好序的有序表（有可能是空表）中, 从而得到一个新的记录数增1的有序表
	 */
	private void charu(int[] a) {
		int len = a.length;
		for (int i = 1; i < len; i++) {
			for (int j = i; j > 0; j--) {
				if (a[j] < a[j - 1]) {
					swap(a, j, j - 1);
				}
			}
		}
		print_array(a);
	}

	/**
	 * 快速排序
	 * 
	 */
	public static void quickSort(String[] strDate, int left, int right) {
		String middle, tempDate;
		int i, j;
		i = left;
		j = right;
		middle = strDate[(i + j) / 2];
		do {
			while (strDate[i].compareTo(middle) < 0 && i < right)
				i++; // 找出左边比中间值大的数
			while (strDate[j].compareTo(middle) > 0 && j > left)
				j--; // 找出右边比中间值小的数
			if (i <= j) { // 将左边大的数和右边小的数进行替换
				tempDate = strDate[i];
				strDate[i] = strDate[j];
				strDate[j] = tempDate;
				i++;
				j--;
			}
		} while (i <= j); // 当两者交错时停止
		// 递归
		if (i < right) {
			quickSort(strDate, i, right);
		}
		if (j > left) {
			quickSort(strDate, left, j);
		}
	}

	/**
	 * 数组反转
	 */
	private void reverse(int[] a) {
		int len = a.length;
		for (int i = 0; i < len / 2; i++) {
			int tmp = a[i];
			a[i] = a[len - i - 1];
			a[len - i - 1] = tmp;
		}
		print_array(a);
	}

	/**
	 * 数组元素交换
	 */
	private void swap(int[] a, int x, int y) {
		int tmp = a[x];
		a[x] = a[y];
		a[y] = tmp;
	}

	/**
	 * 数组打印
	 */
	private void print_array(int[] a) {
		for (int i : a) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	// 冒泡
	public void maoPao(int[] a) {
		for (int i = 1; i < a.length; i++) {
			for (int j = 0; j < a.length - i; j++) {
				if (a[j] > a[j + 1]) {
					int tmp = a[j];
					a[j] = a[j + 1];
					a[j + 1] = tmp;
				}
			}
		}
		System.out.println("冒泡:" + Arrays.toString(a));
	}

	// 选择
	public void xuanZe(int[] a) {
		for (int i = 1; i < a.length; i++) {
			int index = 0;
			for (int j = 0; j <= a.length - i; j++) {
				if (a[j] > a[index]) {
					index = j;
				}
			}
			int tmp = a[a.length - i];
			a[a.length - i] = a[index];
			a[index] = tmp;
		}
	}

	// 插入
	public void chaRu(int[] a) {
		for (int i = 1; i < a.length; i++) {
			for (int j = 0; j < i; j++) {
				if (a[j] > a[i]) {
					int tmp = a[j];
					a[j] = a[i];
					a[i] = tmp;
				}
			}
		}
	}

	// 快速
	public void kuaiSu(int[] a, int low, int high) {
		if (low < high) {
			int i = low;
			int j = high;
			int key = a[i];
			while (i < j) {
				while (i < j && a[j] > key) {
					j--;
				}
				if (i < j) {
					a[i] = a[j];
					i++;
				}
				while (i < j && a[i] < key) {
					i++;
				}
				if (i < j) {
					a[j] = a[i];
				}
			}
			a[i] = key;
			kuaiSu(a, low, i - 1);
			kuaiSu(a, i + 1, high);
		}
	}

}
